﻿using System;

namespace MergeSortAlgorithm
{
    class MergeSortAlgorithm
    {
        static void MergeSort(int[] array, int[] tmpArray, int left, int right)
        {
            if (right <= left)
            {
                return;
            }

            int mid = (left + right) / 2;

            MergeSort(array, tmpArray, left, mid);
            MergeSort(array, tmpArray, mid + 1, right);

            int i, j, k;
            for (i = mid + 1; i > left; i--)
            {
                tmpArray[i - 1] = array[i - 1];
            }

            for (j = mid; j < right; j++)
            {
                tmpArray[right + mid - j] = array[j + 1];
            }

            for (k = left; k <= right; k++)
            {
                array[k] = tmpArray[i] < tmpArray[j] ? tmpArray[i++] : tmpArray[j--];
            }
        }

        static void Main()
        {
            int[] a = { 1, 5, 7, 8, 9, 3, 5, 6, 7 };
            int[] b = new int[a.Length];

            MergeSort(a, b, 0, a.Length - 1);
            foreach (var item in a)
            {
                Console.Write(item);
            }
            Console.WriteLine();
        }
    }
}